package Top_Interview_Questions.Hash_Table;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/9 18:31
 * <p>
 * 功能描述:
 */
public class _0076 {

    public static void main(String[] args) {
        _0076 test = new _0076();
        String s = "EBBANCF";
        String t = "ABC";
        String minWindow = test.minWindow(s, t);
    }

    /**
     * 官方题解的代码
     */
    public String minWindow1(String s, String t) {

        if (s.length() == 0 || t.length() == 0) {
            return "";
        }

        // 字典，它记录了t中所有的唯一字符
        Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }

        // t中唯一字符的数量，这些字符需要出现在所需的窗口中.
        int required = dictT.size();

        // 左右指针
        int l = 0, r = 0;

//        form用来记录t中有多少个唯一字符以期望的频率出现在当前窗口中。
//        如果t是“AABC”，那么窗口必须有两个A，一个B和一个C。当满足所有这些条件时，则得到= 3。
        int formed = 0;

        // 字典，它保存当前窗口中所有唯一字符的计数。
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();

        // form的ans列表(窗口长度，左，右)
        int[] ans = {-1, 0, 0};

        while (r < s.length()) {
            // 从窗口右侧添加一个字符
            char c = s.charAt(r);
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);

//            如果添加的当前字符的频率等于所需的计数，则将形成的计数增加1。
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            // 尽量配合窗户，直到它不再“令人满意”为止。
            while (l <= r && formed == required) {
                c = s.charAt(l);
                // Save the smallest window until now.
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

//                在“左”指针指向的位置上的字符不再是窗口的一部分。
                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }

                // 将左指针向前移动，这将有助于查找新窗口。
                l++;
            }

            // 我们一做完就继续把窗口扩大。
            r++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }


    /**
     * https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/
     * <p>
     * 滑动窗口
     * 不知道为什么执行报错0
     */
    public String minWindow(String s, String t) {
        // 记录最短子串的开始位置和长度
        int start = 0, minLen = Integer.MAX_VALUE;
        int left = 0, right = 0;

        // 相当于两个计数器
        Map<Character, Integer> window = new HashMap<Character, Integer>();
        Map<Character, Integer> needs = new HashMap<Character, Integer>();

        for (int i = 0; i < t.length(); i++) {
            int count = needs.getOrDefault(t.charAt(i), 0);
            needs.put(t.charAt(i), count + 1);
        }

        // 记录 window 中已经有多少字符符合要求了
        int match = 0;

        while (right < s.length()) {
            char c1 = s.charAt(right);
            if (needs.containsKey(c1)) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                /*
                 * window.get(c1) == needs.get(c1)  这样写就报错了
                 * Java 遇到长字符串有问题的，map中取出来的是Integer对象，虽然会自动拆箱，
                 * 但是用 == 作比较的时候也会出问题，使用intValue()方法转换为基本类型，
                 * 详见https://my.oschina.net/miwang/blog/730343
                 */
                if (window.get(c1).compareTo(needs.get(c1)) == 0)
                    // 字符 c1 的出现次数符合要求了
                    match++;
            }
            //right继续前进找可行解
            right++;
            // window 中的字符串已符合 needs 的要求了
            while (match == needs.size()) {
                if (right - left < minLen) {
                    // 更新最小子串的位置和长度
                    start = left;
                    minLen = right - left;
                }
                //开始进行优化，即缩小区间，删除s[left]
                char c2 = s.charAt(left);
                if (needs.containsKey(c2)) {
                    window.put(c2, window.get(c2) - 1);

                    if (window.get(c2) < needs.get(c2))
                        // 字符 c2 出现次数不再符合要求
                        match--;
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, minLen + start);
    }

}
